package backtrack;
import java.util.*;
public class _03_17_电话号码的字母组合 {
	Map<String,String> map = new HashMap<>();
	char c[];
	String s[]; // 存储了digit的每个数字转化后的字符串
	StringBuilder item = new StringBuilder();
	List<String> list = new ArrayList<>();
	// 初始化
	public void init(String digits) {
    	map.put("2", "abc");
    	map.put("3", "def");
    	map.put("4", "ghi");
    	map.put("5", "jkl");
    	map.put("6", "mno");
    	map.put("7", "pqrs");
    	map.put("8", "tuv");
    	map.put("9", "wxyz");
    	c = digits.toCharArray();
    	s = new String[c.length];
    	for(int i = 0; i < c.length; i++) {
    		s[i] = map.get(String.valueOf(c[i]));
    	}
	}
	// index用来控制遍历到哪个数字对应的字符串
	public void backtracking(int index) {
		if(index == s.length) {
			// 当digit为""，长度为0，这里会add一个空串，导致长度为1
			if(item.length() != 0) {
				list.add(item.toString());
			}
			return;
		}
		// 取出当前的字符串
		String str = s[index];
		for(int i = 0; i < str.length(); i++) {
			item.append(str.charAt(i));
			backtracking(index + 1);
			item.deleteCharAt(item.length() - 1);
		}
		
	}
	
    public List<String> letterCombinations(String digits) {
    	init(digits);
    	backtracking(0);
    	return list;
    }
    
    public static void main(String[] args) {
    	new _03_17_电话号码的字母组合().letterCombinations("");
	}
}
